package impl;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Keevu
 * Date: 07/09/11
 * Time: 14:21
 * To change this template use File | Settings | File Templates.
 */

public class QuickSorter extends AbstractSorter {
    public QuickSorter() {
        super(SorterType.QUICK);
    }

    public <T> void sort(Comparator<T> comparator, List<T> list) {

        miniSort(comparator, list, 0, list.size() - 1);
    }

    private <T> void miniSort(Comparator<T> comparator, List<T> list, int inicio, int fin) {

        if (inicio >= fin) return;

        int ki = inicio - 1;
        int kj = fin;

        while (true) {

            while (greater(comparator, list, fin, ++ki)) {
                if (ki == fin) {
                    break;
                }
            }
            while (greater(comparator, list, --kj, fin)) {
                if (kj <= inicio) {
                    break;
                }
            }
            if ((kj <= ki)) {
                swap(list, ki, fin);
                break;
            } else {
                swap(list, ki, kj);
            }

        }
        miniSort(comparator, list, inicio, ki - 1);
        miniSort(comparator, list, ki + 1, fin);

    }
}